package com.btashov.linkedlist;

import com.btashov.datastructure.LinkedListNode;
import com.btashov.datastructure.Node;

/**
 * todo: 2.4 You have two numbers represented by a linked list, where each node contains a single digit.
 * The digits are stored in reverse order, such that the 1’s digit is at the head of the list.
 * Write a function that adds the two numbers and returns the sum as a linked list.
 */
public class SumLinkedListNode {

    /**
     * Adds the two numbers and returns the sum as a linked list.
     * <p/>
     * Two numbers represented by a linked list, where each node contains a single digit.
     * The digits are stored in reverse order, such that the 1’s digit is at the head of the list.
     * <p/>
     * <p/>
     * SOLUTION
     * We can implement this recursively by adding node by node, just as we would digit by digit.
     * 1. result.data = (node1 + node2 + any earlier carry) % 10
     * 2. if node1 + node2 > 10, then carry a 1 to the next addition.
     * 3. add the tails of the two nodes, passing along the carry.
     * <p/>
     * EXAMPLE
     * Input: (3 -> 1 -> 5), (5 -> 9 -> 2)
     * Output: 8 -> 0 -> 8
     *
     * @param listA LinkedListNode
     * @param listB LinkedListNode
     * @return sum of nodes in LinkedListNode
     */
    public LinkedListNode addNumbers(LinkedListNode listA, LinkedListNode listB) {
        if (listA == null && listB == null) {
            throw new IllegalArgumentException("both lists cannot be null");
        }

        if (listA == null) {
            return listB;
        }
        if (listB == null) {
            return listA;
        }

        LinkedListNode resultList = new LinkedListNode();
        addNumbers(listA.getHead(), listB.getHead(), 0, resultList);
        return resultList;
    }


    private void addNumbers(Node nodeA, Node nodeB, int carry, LinkedListNode resultList) {
        if (nodeA == null && nodeB == null) return;

        int sum = carry;

        if (nodeA != null) {
            sum += nodeA.getId();
        }

        if (nodeB != null) {
            sum += nodeB.getId();
        }

        carry = 0;
        if (sum >= 10) {
            sum = sum % 10;
            carry = 1;
        }

        Node nextNode1 = (nodeA == null) ? null : nodeA.getNext();
        Node nextNode2 = (nodeB == null) ? null : nodeB.getNext();
        addNumbers(nextNode1, nextNode2, carry, resultList);
        resultList.append(new Node(sum));
    }
}
